package com.wq.sort;

/**
 * @Author: wangqiang20995
 * @Date:2019/4/1
 * @Description:
 * @Resource:
 */
public class ShellSort extends BaseSort {
    public ShellSort(int size) {
        super(size);
    }

    public static void main(String[] args){
        ShellSort shellSort = new ShellSort(1000000);
//        shellSort.printArray(true);
        long start = System.currentTimeMillis();
        shellSort.shellSort();
        long end = System.currentTimeMillis();
//        shellSort.printArray(true);
        System.out.println("cost:" + (end - start));
    }
    public void shellSort() {
        //获取shell排序的第一次的步长
        int step = findMaxStep(array.length);

        /**
         * 以后每一次排序的步长，都是前一次的(步长-1)/3,逐渐减小每一次排序的步长
         */
        while (step > 0) {
            //这个循环：在这一次shell排序内，也就是当前这个步长，对每一组下表间隔为step的数据进行直接插入排序
            for (int i = 0; i < step; i++) {
                directInsert(step, i);
            }

            step = (step - 1)/3;
        }
    }

    /**
     * 直接插入排序，开始下标为begin，步长为step
     * @param step
     * @param begin
     */
    private void directInsert(int step, int begin) {
        int nextIndex = begin + step;

        /**
         * 第一次循环，其实排的是begin这个下标的数据，第二次排的是[begin,begin+step]，第三次是[begin,begin+step,begin+2*step]...[begin,begin+step,...,begin+(i-1)*step]
         * begin+(i-1)*step < array.length
         */
        while (nextIndex < array.length){
            int temp = array[nextIndex];
            int preIndex = nextIndex - step;
            /**
             * 这个循环的含义就是在这一次插入排序的过程中，假设array[0],...,array[i]都是有序的，将数字M插入到array中去
             * 得到array[0],...array[x]=M,...,array[i]
             */
            while (preIndex >= 0 && array[preIndex] > temp){
                array[preIndex + step] = array[preIndex];
                preIndex -= step;
            }

            array[preIndex + step] = temp;
            nextIndex = nextIndex + step;
        }
    }

    int findMaxStep(int size) {
        int h = 1;
        while ((3 * h + 1) < size) {
            h = 3 * h + 1;
        }
        return h;
    }
}
